#include <iostream>
#include <set>
#include <map>
//#include <multiset>
//#include <multimap>
using namespace std;

//template<class T>     // 应定义容器
//void display(Container<T>){  应将Container作为模板参数

template<typename Container>
void display(const Container& container){
    for(auto & elem : container){
        cout << elem << " ";
    }

    cout << endl;
}

template<typename Key, typename Value>
void display(const map<Key, Value>& container){
    for(auto & elem : container){
        cout << elem.first << ":" << elem.second << " ";
    }

    cout << endl;
}

template<typename Key, typename Value>
void display(const multimap<Key, Value>& container){
    for(auto & elem : container){
        cout << elem.first << ":" << elem.second << " ";
    }

    cout << endl;
}

void set_test(){
    cout << "=====set_test=====" << endl;

    // 1. 初始化
    set<int> number = {1, 3, 4, 8, 7, 3, 4, 9};
    display(number);

    // 2. 查找
    size_t cnt = number.count(3);
    cout << "cnt = " << cnt << '\n';    // 返回1，表示元素存在
    
    set<int>::iterator it = number.find(6);
    it == number.end() ? cout << "不在\n" : cout << "存在\n";

    // 3. 插入
    pair<set<int>::iterator, bool> ret = number.insert(6);
    ret.second ? cout << "不在序列，插入成功\n" : cout << "已在序列，插入失败\n";

    // 4. 删除
    number.erase(7);
    display(number);

    for(auto it = number.begin(); it != number.end();){
        if((*it & 1) == 1){
            number.erase(it++);
        }
        else{
            ++it;
        }
    }
    display(number);

    // 5. 下标访问
//    cout << "number[2] = " << number[2] << endl;
}

void multiset_test(){
    cout << "=====multiset_test=====" << endl;
    
    // 1. 初始化
    multiset<int> number = {1, 3, 4, 8, 7, 3, 4, 9};
    display(number);

    // 2. 查找
    size_t cnt = number.count(3);
    cout << "cnt = " << cnt << '\n';    // 返回1，表示元素存在
    
    multiset<int>::iterator it = number.find(6);
    it == number.end() ? cout << "不在\n" : cout << "存在\n";

    // 3. 插入
    number.insert(6);

    // 4. 删除
    number.erase(7);
    display(number);

    for(auto it = number.begin(); it != number.end();){
        if((*it & 1) == 1){
            number.erase(it++);
        }
        else{
            ++it;
        }
    }
    display(number);

    // 5. 下标访问
//    cout << "number[2] = " << number[2] << endl;

    // 6. bound系列
    auto cit = number.lower_bound(4);   // >= key
    auto cit2 = number.upper_bound(4);  // > key
    cout << "*cit = " << *cit << endl;
    cout << "*cit2 = " << *cit2 << endl;
    while(cit != cit2){
        cout << *cit << " ";
        ++cit;
    }
    cout << '\n';

    pair<multiset<int>::iterator, multiset<int>::iterator> ret1 
        = number.equal_range(4);
    while(ret1.first != ret1.second){
        cout << *ret1.first << " ";
        ++ret1.first;
    }
    cout << '\n';
}

void map_test(){
    cout << "=====map_test=====" << endl;

    // 1. 初始化
    map<int, string> number = {
        {1, "北京"},
        {3, "南京"},
        pair<int, string>{4, "武汉"},
        pair<int, string>{2, "武汉"},
        make_pair(5, "天津"),
        make_pair(3, "湖南"),
    };
    display(number);

    // 2. 查找
    size_t cnt = number.count(3);
    cout << "cnt = " << cnt << '\n';    // 返回1，表示元素存在
    
    map<int, string>::iterator it = number.find(6);
    it == number.end() ? cout << "不在\n" : cout << "存在\n";

    // 3. 插入
    pair<map<int, string>::iterator, bool> ret = number.insert({6, "东京"});
    ret.second ? cout << "不在序列，插入成功\n" : cout << "已在序列，插入失败\n";

    // 4. 删除
    number.erase(7);
    display(number);

    for(auto it = number.begin(); it != number.end();){
        if(((*it).first & 1) == 1){
            number.erase(it++);
        }
        else{
            ++it;
        }
    }
    display(number);

    // 5. 下标访问
    cout << "number[4] = " << number[4] << endl;   // 查找
    cout << "number[8] = " << number[8] << endl;   // 插入
    display(number);

    number[8] = "重庆";
    number[7] = "上海";
    display(number);
}

void multimap_test(){
    cout << "=====multimap_test=====" << endl;

    // 1. 初始化
    multimap<int, string> number = {
        {1, "北京"},
        {3, "南京"},
        pair<int, string>{4, "武汉"},
        pair<int, string>{2, "武汉"},
        make_pair(5, "天津"),
        make_pair(3, "湖南"),
    };
    display(number);

    // 2. 查找
    size_t cnt = number.count(3);
    cout << "cnt = " << cnt << '\n';    // 返回1，表示元素存在
    
    multimap<int, string>::iterator it = number.find(6);
    it == number.end() ? cout << "不在\n" : cout << "存在\n";

    // 3. 插入
//    pair<multimap<int, string>::iterator, bool> ret = number.insert({6, "东京"});
    number.insert({6, "东京"});

    // 4. 删除
    number.erase(7);
    display(number);

    for(auto it = number.begin(); it != number.end();){
        if(((*it).first & 1) == 1){
            number.erase(it++);
        }
        else{
            ++it;
        }
    }
    display(number);

    // 5. 下标访问
//    cout << "number[4] = " << number[4] << endl;   // 查找
//    cout << "number[8] = " << number[8] << endl;   // 插入
//    display(number);
//
//    number[8] = "重庆";
//    number[7] = "上海";
//    display(number);
}

int main()
{
    set_test();
    multiset_test();
    map_test();
    multimap_test();    

    return 0;
}

